//题目:
// 给定一个由 不同 正整数组成的数组 nums ，和一个目标整数 target 。
// 请从 nums 中找出并返回总和为 target 的元素组合的个数。
// 数组中的数字可以在一次排列中出现任意次，但是顺序不同的序列被视作不同的组合。

// 题目数据保证答案符合 32 位整数范围。
#include<iostream>
#include<vector>

using namespace std;
//代码
class Solution 
{
public:
    int combinationSum4(vector<int>& nums, int target) 
    {
        //假设，不看顺序，仅看组合
        // //1.创建dp表————dp[i][j]表示:选到第i个元素，和为j时，最大组合数
        // int n=nums.size();
        // vector<vector<int>> dp(n+1,vector<int>(target+1));
        // //2.初始化
        // dp[0][0]=1;
        // //3.填表————动态转移方程：dp[i][j]+=dp[i-1][j-k*nums[i]];
        // for(int i=1;i<=n;i++)
        // {
        //     for(int j=0;j<=target;j++)
        //     {
        //         for(int k=0;k*nums[i-1]<=j;k++)
        //             dp[i][j]+=dp[i-1][j-k*nums[i-1]];
        //     }
        // }
        // //4.确定返回值
        // return dp[n][target];

        //1.创建一个dp表————dp[j][i]表示：总和为j时，排列数的个数
        vector<double> dp(target+1);
        //2.初始化
        dp[0]=1;
        //3.填表————if(j-nums[i]) dp[j]+=dp[j-nums[i]];
        for(int j=1;j<=target;j++)
            for(int i=0;i<nums.size();i++)
                if(j-nums[i]>=0)
                    dp[j]+=dp[j-nums[i]];
        //4.确定返回值
        return dp[target];
    }
};